package com.leon.alishop.spider.bucket;

import java.security.MessageDigest;
import java.util.Arrays;
import java.util.BitSet;

/**
 * 
 * 通过MD5算法进行string的去重工作<br>
 * 非线程安全<br>
 * 最多承载量级千万<br>
 * 此算法采用开放地址法进行hash存储，并采用二次探测法解决哈希冲突<br>
 * 
 * @author Leon
 *
 */
public class MultStringBucket {

	/**
	 * 存储table
	 */
	private transient byte[] table;
	
	/**
	 * 溢出table<br>
	 * 除了null，基本不会用到这个table，所以操作不写严格的了，需要再扩展。
	 */
	private transient String[] overflowTable;
	
	/**
	 * 记录删除标志位
	 */
	private transient BitSet removeBitSet;
	
	/**
	 * MD5为byte16步长
	 */
	private static final int MD5_STEP = 16;
	
	/**
	 * 默认的模长
	 */
	private static final int DEFAULT_INITIAL_CAPACITY = 19;
	
	/**
	 * 最大的模长
	 */
	private static final int MAXIMUM_CAPACITY = 0x7FFFFD9;
	
	/**
	 * 负荷系数
	 */
	private static final float DEFAULT_LOAD_FACTOR = 0.85f;
	
	/**
	 * 当前模长
	 */
	transient volatile int modCount;
	
	/**
	 * 大小
	 */
	transient int size;
	
	/**
	 * 删除大小
	 */
	transient int removeSize;
	
	/**
	 * 溢出大小
	 */
	transient int overflowSize;
	
	/**
	 * 负载因子
	 */
	private final float loadFactor;
	
	/**
	 * 最大容量值，超过则进行resize
	 */
	private int threshold;
	
	/**
	 * 查询因子
	 */
	private int lookupFactor;
	
	/**
	 * 默认大小为 19，默认负载因子为0.85
	 * 注意：resize会带来资源开销，最好选择合适的初始化大小
	 */
	@Deprecated
	public MultStringBucket(){
		this.modCount=DEFAULT_INITIAL_CAPACITY;
		this.table = new byte[this.modCount<<4];
		this.removeBitSet = new BitSet(this.modCount);
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		this.threshold  = (int) (DEFAULT_INITIAL_CAPACITY * loadFactor);
	}
	
	/**
	 * @param initialCapacity 初始化大小
	 */
	public MultStringBucket(int initialCapacity){
		if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
		this.modCount = nextModule(initialCapacity < 3 ? 7 : initialCapacity,1);
		this.table = new byte[this.modCount<<4];
		this.removeBitSet = new BitSet(this.modCount);
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		this.threshold = (int) (this.modCount * this.loadFactor);
	}
	
	/**
	 * @param initialCapacity 初始化大小
	 * @param loadFactor 负载因子
	 */
	public MultStringBucket(int initialCapacity, float loadFactor){
		if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
		if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
		this.modCount = nextModule(initialCapacity < 3 ? 3 : 7,1);
		this.table = new byte[this.modCount<<4];
		this.removeBitSet = new BitSet(this.modCount);
		this.loadFactor = loadFactor;
		this.threshold = (int) (this.modCount * loadFactor);
	}
	
	/**
	 * 获取下一个有效的质数<br>
	 * 扩展模长系数为原来的2倍
	 * @param modCount 
	 * @param step
	 * @return
	 */
	private int nextModule(int modCount,int step){
		this.lookupFactor = (int)(modCount*step-3)/4+1;
		if(this.lookupFactor<0)
			return MAXIMUM_CAPACITY;
		int m;
		while((m=((this.lookupFactor<<2)+3))>0 
				&& !isPrime(m)){
			this.lookupFactor++;
		}
		return m;
	}
	
	/**
	 * 判断是否为质数
	 * @param number
	 * @return
	 */
	private static boolean isPrime(int number){
		if(number < 2)
			return false;
		double sqrt = Math.sqrt(number);
		for (int i = 2; i <= sqrt; i++) {
			if(number%i==0)
				return false;
		}
		return true;
	}
	
	/**
	 * 大小
	 * @return
	 */
	public int size(){
		return size + overflowSize - removeSize;
	}
	
	/**
	 * 是否包含字符串
	 * @param value
	 * @return
	 */
	public boolean contains(String value){
		if(value == null
				|| value.length()==0)
			return containsIllegalValue(value);
		byte[] md5 = getMD5ByteArr(value);
		if(!isValidMd5(md5))
			return containsIllegalValue(value);
		return containsMd5(md5);
	}
	
	private boolean containsIllegalValue(String value){
		for (int i = 0; i < overflowSize; i++) {
			if(overflowTable[i] == value
					|| (value!=null && value.equals(overflowTable[i])))
				return true;
		}
		return false;
	}
	
	
	private boolean containsMd5(byte[] md5){
		int pos=indexFor(hashMd5(md5), modCount);
		switch (eqOrEmptyMd5(pos, md5)) {
		case 0:
			return false;
		case 1:
			break;
		case 2:
			return !removeBitSet.get(pos);
		}
		for(int k=1,pow,formax=modCount>>1,actpos;k<=formax;k++){
			pow = (int)Math.pow(k, 2);
			switch (eqOrEmptyMd5(actpos = indexSearchFor(pos, pow, modCount), md5)) {
			case 0:
				return false;
			case 1:
				break;
			case 2:
				return !removeBitSet.get(actpos);
			}
			switch (eqOrEmptyMd5(actpos = indexSearchFor(pos, -pow, modCount), md5)) {
			case 0:
				return false;
			case 1:
				break;
			case 2:
				return !removeBitSet.get(actpos);
			}
		}
		return false;
	}
	
	/**
	 * 增加字符串
	 * @param value
	 * @return
	 */
	public boolean add(String value){
		if(size == modCount)
			throw new ArrayIndexOutOfBoundsException();
		if(value == null
				|| value.length()==0)
			return addIllegalValue(value);
		byte[] md5 = getMD5ByteArr(value);
		if(!isValidMd5(md5))
			return addIllegalValue(value);
		addMd5(md5);
		if(size >= threshold && modCount != MAXIMUM_CAPACITY)
			return resize();
		return true;
	}
	
	
	/**
	 * 增加单条md5
	 * @param md5
	 */
	private boolean addMd5(byte[] md5){
		int pos=indexFor(hashMd5(md5), modCount);
		if(addMd5IfEqOrEmpty(pos, md5))
			return true;
		for(int k=1,pow,formax=modCount>>1;k<=formax;k++){
			pow = (int)Math.pow(k, 2);
			if(addMd5IfEqOrEmpty(indexSearchFor(pos, pow, modCount), md5)
					|| addMd5IfEqOrEmpty(indexSearchFor(pos, -pow, modCount), md5))
				return true;
		}
		return false;
	}
	
	/**
	 * 是否相等
	 * @param oriPos
	 * @param md5
	 * @return
	 */
	@SuppressWarnings("unused")
	private boolean eqMd5(int oriPos, byte[] md5){
		oriPos<<=4;
		for (int i=0; i<MD5_STEP; i++,oriPos++) 
			if(table[oriPos] != md5[i])
				return false;
		return true;
	}
	
	/**
	 * 0-空，1-不相等，2-相等
	 * @param oriPos
	 * @param md5
	 * @return
	 */
	private int eqOrEmptyMd5(int oriPos, byte[] md5){
		oriPos<<=4;
		boolean eq=true,empty=true;
		for (int i=0; i<MD5_STEP && (eq || empty); i++,oriPos++){
			if(table[oriPos] != 0)
				empty=false;
			if(table[oriPos] != md5[i])
				eq=false;
		}
			
		return empty ? 0 : (eq ? 2 : 1);
	}
	
	private boolean addMd5IfEqOrEmpty(int oriPos, byte[] md5){
		boolean eq=true,empty=true;
		for (int i=0,index=oriPos<<=4; i<MD5_STEP && (eq || empty); i++,index++) {
			if(table[index]!=0)
				empty = false;
			if(table[index]!=md5[i])
				eq = false;
		}
		if(eq){
			if(removeBitSet.get(oriPos)){
				removeSize--;
				removeBitSet.set(oriPos, false);
			}
			return true;
		}
		if(empty){
			this.size++;
			System.arraycopy(md5, 0, table, oriPos, MD5_STEP);
			return true;
		}
		return false;
	}
	
	/**
	 * 重新设置table的大小
	 */
	private boolean resize(){
		if (this.modCount == MAXIMUM_CAPACITY)
			return true;
		int nextSize = nextModule(this.modCount, 3);
		System.out.println("开始resize:"+nextSize);
		long start = System.currentTimeMillis();
		byte[] oritable = table;
		int oriModCount = this.modCount;
		this.table = new byte[nextSize<<4];
		this.modCount = nextSize;
		this.removeSize=0;
		this.size=0;
		this.threshold = (int) (modCount*loadFactor);
		this.removeBitSet = new BitSet(nextSize);
		byte[] ba = new byte[MD5_STEP];
		boolean valid = false;
		for (int i = 0,j = 0; i < oriModCount; i++,j=i<<4) {
			if(removeBitSet.get(i))
				continue;
			for (int a = 0; a < MD5_STEP; a++) {
				ba[a] = oritable[j+a];
				if(ba[a] != 0)
					valid = true;
			}
			if(valid)
				addMd5(ba);
			valid = false;
		}
		ba = null;
		oritable = null;
		System.out.println("结束resize:"+(System.currentTimeMillis() - start));
		return true;
	}
	
	private static int indexSearchFor(int pos,int offset,int len){
		int spos = (int) (offset >= 0 ?
				(pos + (long)Math.pow(offset, 2))%len : 
					(pos - (long)Math.pow(offset, 2)%len));
		return spos >= 0 ? spos : len + spos;
	}
	
	
	/**
	 * 是否是有效的MD5<br>
	 * null/0
	 * @param md5
	 * @return
	 */
	private static boolean isValidMd5(byte[] md5){
		if(null != md5
				&& md5.length==MD5_STEP)
			for (int i = 0; i < MD5_STEP; i++)
				if(md5[i]!=0)
					return true;
		return false;
	}
	
	/**
	 * 溢出table，即无效的md5存储
	 * @param value
	 * @return
	 */
	private boolean addIllegalValue(String value){
		if(null == overflowTable){
			overflowTable = new String[]{value};
			return true;
		}
		int len=overflowTable.length;
		if(value == null)
		for (int i = 0; i < len; i++) {
			if(value == overflowTable[i]
					|| (null != value && value.equals(overflowTable[i])))
				return true;
		}
		String[] temp = Arrays.copyOf(overflowTable, len+1);
		temp[len] = value;
		overflowSize++;
		return true;
	}
	
	/**
	 * 移除元素
	 * @param value
	 * @return
	 */
	public boolean remove(String value){
		if(null == value
				|| value.length()==0)
			return removeIllegalValue(value);
		byte[] md5 = getMD5ByteArr(value);
		if(!isValidMd5(md5))
			return removeIllegalValue(value);
		return removeMd5(md5);
	}
	
	private boolean removeMd5(byte[] md5){
		int pos=indexFor(hashMd5(md5), modCount);
		switch (eqOrEmptyMd5(pos, md5)) {
		case 0:
			return true;
		case 1:
			break;
		case 2:
			if(!removeBitSet.get(pos)){
				removeBitSet.set(pos);
				removeSize++;
			}
			return true;
		}
		for(int k=1,pow,formax=modCount>>1,actpos;k<=formax;k++){
			pow = (int)Math.pow(k, 2);
			switch (eqOrEmptyMd5(actpos = indexSearchFor(pos, pow, modCount), md5)) {
			case 0:
				return true;
			case 1:
				break;
			case 2:
				if(!removeBitSet.get(actpos)){
					removeBitSet.set(actpos);
					removeSize++;
				}
				return true;
			}
			switch (eqOrEmptyMd5(actpos = indexSearchFor(pos, -pow, modCount), md5)) {
			case 0:
				return true;
			case 1:
				break;
			case 2:
				if(!removeBitSet.get(actpos)){
					removeBitSet.set(actpos);
					removeSize++;
				}
				return true;
			}
		}
		return true;
	}
	
	private boolean removeIllegalValue(String value){
		if(null == overflowTable)
			return true;
		boolean has = false;
		int len = overflowTable.length;
		int same = 0;
		for (; same < len; same++)
			if(value == overflowTable[same]
					||(null != value && value.equals(overflowTable[same]))){
				has = true;
				break;
			}
		if(has){
			String[] newtemp = new String[len-1];
			for (int i=0,j=0; i < len; i++)
				if(i != same)
					newtemp[j++]=overflowTable[i];
			overflowTable = newtemp;
		}
		return true;
	}
	
	private static int hashMd5(byte[] md5){
		int h = Arrays.hashCode(md5);
		h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
	}
	
	private static int indexFor(int hash,int len){
//		int out = hash^(hash>>>=31);
//		out = out-hash;
		return Math.abs(hash)%len;
	}
	
	private static byte[] getMD5ByteArr(String str){
//		if (str == null || str.length() == 0)
//			throw new IllegalArgumentException("String to encript cannot be null or zero length");
		try {
			MessageDigest digest = MessageDigest.getInstance("MD5");
			digest.update(str.getBytes("UTF-16"));
			return digest.digest();
		} catch (Exception e) {
			// ignore this exception
			e.printStackTrace();
		}
		return null;
	}

}
